#include <bits/stdc++.h>
#include "BalanceTree.h"
using namespace std;



template <class T>
void AVL_sort(vector <T> & data){
	AvlTree <T> t;
	for(int i = 0; i < data.size(); ++i) t.insert(data[i]);
	data.clear();
	t.intoTree(data);
}
	template <class T>
void Splay_sort(vector <T> & data){
	SplayTree <T> t;
	for(int i = 0; i < data.size(); ++i) t.insert(data[i]);
	data.clear();
	t.intoTree(data);
}
 

int n;
vector <int> data, temp;
int main() {
	cin >> n;
	data.resize(n);
	for(int i = 0; i < n; ++i)  data[i]=rand();
    for(int i=0;i<n;i++) cout<< data[i] <<' ';
    cout << endl;
	
	double begin, end;
	temp = data;
	begin = clock();
	AVL_sort(temp);
	end = clock();

    for(int i=0;i<n;i++) cout << temp[i] << ' ';
	cout << endl;
	cout << "AVL_sort: time = " << end - begin << endl;
	
	temp = data;
	begin = clock();
	Splay_sort(temp);
	end = clock();
	for(int i=0;i<n;i++) cout << temp[i] << ' ';
	cout << endl;
	cout << "Splay_sort: time = " << end - begin << endl;
}